//
// Created by Administrator on 2021/9/27.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int MOD = 1'000'000'000 + 7;

    int numDecodings(string s) {
        int n = static_cast<int>(s.size());
        vector<long long> dp(n + 1, 0);
        dp[0] = 1;
        if (s[0] == '*') {
            dp[1] = 9;
        } else if (s[0] == '0') {
            return 0;
        } else {
            dp[1] = 1;
        }
        int k1 = 0, k2 = 0;
        for (int i = 2; i <= n; ++i) {
            char ch1 = s[i - 1];   // 这一位
            char ch2 = s[i - 2];   // 前一位
            if (ch1 == '0') k1 = 0;
            else if (ch1 == '*') k1 = 9;
            else k1 = 1;
            if (ch2 == '*') {
                if (ch1 >= '0' and ch1 <= '6') {
                    k2 = 2;
                } else if (ch1 >= '7' and ch1 <= '9') {
                    k2 = 1;
                } else {
                    k2 = 15;
                }
            } else {
                if (ch2 == '0') k2 = 0;
                else if (ch2 == '1') {
                    if (ch1 == '*') k2 = 9;
                    else k2 = 1;
                } else if (ch2 == '2') {
                    if (ch1 == '*') k2 = 6;
                    else if (ch1 >= '0' and ch1 <= '6') k2 = 1;
                    else k2 = 0;
                } else if (ch2 >= '3' and ch2 <= '9') k2 = 0;
            }
            dp[i] = (dp[i - 1] * k1 % MOD + dp[i - 2] * k2 % MOD) % MOD;
        }
        return (int) dp.back();
    }
};

class Solution2 {
public:
    int MOD = 1'000'000'000 + 7;

    int numDecodings(string s) {
        int n = static_cast<int>(s.size());
        long long a = 0, b = 0, c = 0;
        a = 1;
        if (s[0] == '*') {
            b = 9;
        } else if (s[0] == '0') {
            return 0;
        } else {
            b = 1;
        }
        int k1 = 0, k2 = 0;
        for (int i = 2; i <= n; ++i) {
            char ch1 = s[i - 1];   // 这一位
            char ch2 = s[i - 2];   // 前一位
            if (ch1 == '0') k1 = 0;
            else if (ch1 == '*') k1 = 9;
            else k1 = 1;
            if (ch2 == '*') {
                if (ch1 >= '0' and ch1 <= '6') {
                    k2 = 2;
                } else if (ch1 >= '7' and ch1 <= '9') {
                    k2 = 1;
                } else {
                    k2 = 15;
                }
            } else {
                if (ch2 == '0') k2 = 0;
                else if (ch2 == '1') {
                    if (ch1 == '*') k2 = 9;
                    else k2 = 1;
                } else if (ch2 == '2') {
                    if (ch1 == '*') k2 = 6;
                    else if (ch1 >= '0' and ch1 <= '6') k2 = 1;
                    else k2 = 0;
                } else if (ch2 >= '3' and ch2 <= '9') k2 = 0;
            }
            c = (b * k1 % MOD + a * k2 % MOD) % MOD;
            a = b;
            b = c;
        }
        return (int) c;
    }
};
class Solution3 {
private:
    static constexpr int mod = 1000000007;

public:
    int numDecodings(string s) {
        auto check1digit = [](char ch) -> int {
            if (ch == '0') {
                return 0;
            }
            return ch == '*' ? 9 : 1;
        };

        auto check2digits = [](char c0, char c1) -> int {
            if (c0 == '*' && c1 == '*') {
                return 15;
            }
            if (c0 == '*') {
                return c1 <= '6' ? 2 : 1;
            }
            if (c1 == '*') {
                if (c0 == '1') {
                    return 9;
                }
                if (c0 == '2') {
                    return 6;
                }
                return 0;
            }
            return c0 != '0' && (c0 - '0') * 10 + (c1 - '0') <= 26;
        };

        int n = s.size();
        // a = f[i-2], b = f[i-1], c = f[i]
        int a = 0, b = 1, c = 0;
        for (int i = 1; i <= n; ++i) {
            c = (long long)b * check1digit(s[i - 1]) % mod;
            if (i > 1) {
                c = (c + (long long)a * check2digits(s[i - 2], s[i - 1])) % mod;
            }
            a = b;
            b = c;
        }
        return c;
    }
};

int main() {
    Solution3 solution;
    cout << solution.numDecodings("1*72*") << endl;
    cout << solution.numDecodings("7*9*3*6*3*0*5*4*9*7*3*7*1*8*3*2*0*0*6*") << endl;
    return 0;

}
